# dwg的类实现在上一章节的文件中
from MultiSegmentGraphSolution import DirectedWeightGraph

n = 3  # 图中的顶点个数

# 初始化有向加权图dwg
dwg = DirectedWeightGraph(n)
dwg.addEdge(0, 1, 4)
dwg.addEdge(1, 0, 6)
dwg.addEdge(0, 2, 11)
dwg.addEdge(2, 0, 3)
dwg.addEdge(1, 2, 2)

# 初始化代价矩阵cost[n][n]
cost = [list(r) for r in dwg.edges]

# 算法最核心的5行代码，对cost数组进行n次迭代
for k in range(n):
    for i in range(n):
        for j in range(n):
            # 如果从vi经过k，到达vj的路径更短，则更新<vi,vj>的权重
            if cost[i][k] + cost[k][j] < cost[i][j]:
                cost[i][j] = cost[i][k] + cost[k][j]

# 输出最短路径长度
for i in range(n):
    for j in range(n):
        if i != j:
            print(f'{i} -> {j} 最短路径长度：{cost[i][j]}')
